import java.util.*;

public class dome {
    public static void main(String[] args) {
        
    }

    static public int longestWPI(int[] hours) {
        int n = hours.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int s = 0, res = 0;
        for (int i = 0; i < n; i++) {
            s += hours[i] > 8 ? 1 : -1;
            if (s > 0) {
                res = Math.max(res, i + 1);//合法时间段[0, i]
            } else {//[0, i]不合法
                //判断是否存在[0, j] = s - 1; [0, i]丢弃[0, j]，即s - (s - 1) = 合法
                if (map.containsKey(s - 1)) {
                    res = Math.max(res, i - map.get(s - 1));
                }
            }
            if (!map.containsKey(s)) {
                map.put(s, i);
            }
        }
        return res;
    }
    static public int numSubarrayProductLessThanK(int[] nums, int k) {
        int l = 0, r = 0, res = 0, curVal = 1;
        while(r < nums.length){
            curVal *= nums[r];
            while(l <= r && curVal >= k){
                curVal /= nums[l++];
            }
            res += r - l + 1;
            r++;
        }
        return res;
    }
    static public int minMoves(int[] nums, int k) {
        int n = nums.length;
        int[] preSum = new int[n + 1];
        int res = nums.length;
        for(int i = 1; i < preSum.length; i++){
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for(int i = 1; i < preSum.length; i++){
            for(int j = i + k - 1; j < preSum.length; j++){
                if(preSum[j] - preSum[i - 1] == k){
                    int cur = find(nums, i - 1, j - 1);
                    res = Math.min(res, cur);
                }
            }
        }
        return res;
    }

    static public int find(int[] nums, int l, int r){
        int[] cost = new int[r - l + 1];
        int oneNum = 0, res = 0;
        for(int i = l; i <= r; i++){
            if(nums[i] == 1){
                oneNum++;
            }else{
                cost[i - l] = cost[i - l] == 0 ? oneNum : Math.min(oneNum, cost[i - l]);
            }
        }
        oneNum = 0;
        for(int i = r; i >= l; i--){
            if(nums[i] == 1){
                oneNum++;
            }else{
                cost[i - l] = cost[i - l] == 0 ? oneNum : Math.min(oneNum, cost[i - l]);
                res += cost[i - l];
            }
        }
        return res;
    }
    static public boolean strongPasswordCheckerII(String password) {
        if(password.length() < 8){
            return false;
        }
        int res = 0;
        Set<Character> set = new HashSet<>();
        String str = "!@#$%^&*()-+";
        for(int i = 0; i < str.length(); i++){
            set.add(str.charAt(i));
        }
        for(int i = 0; i < password.length(); i++){
            char curCh = password.charAt(i);
            if(i > 0 && curCh == password.charAt(i - 1)){
                return false;
            }
            if(curCh >= 'a' && curCh <= 'z'){
                res |= 1;
            }
            if(curCh >= 'A' && curCh <= 'Z'){
                res |= (1 << 1);
            }
            if(curCh >= '0' && curCh <= '9'){
                res |= (1 << 2);
            }
            if(set.contains(curCh)){
                res |= (1 << 3);
            }
        }
        return res == (1 << 4) - 1;
    }
    static public int translateNum(int num) {
        if(num < 10){
            return 1;
        }
        if(num >= 10 && num < 26){
            return 2;
        }
        int cur = num;
        int ind = 1;
        while(cur > 25){
            ind *= 10;
            cur /= 10;
        }
        if(cur < 10){
            return translateNum(num - cur * ind);
        }else{
            int n1 = translateNum(num - cur / 10 * ind * 10);
            int n2 = translateNum(num - cur * ind);
            return n1 + n2;
        }
    }
    static public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                boolean[][] visited = new boolean[board.length][board[0].length];
                if(dfs(board, i, j, 0, word, visited)){
                    return true;
                }
            }
        }
        return false;
    }

    static boolean dfs(char[][] board, int i, int j, int index, String word, boolean[][] visited){
        int m = board.length, n = board[0].length;
        if(index == word.length()){
            return true;
        }
        if(i < 0 || i >= m || j < 0 || j >= n){
            return false;
        }
        if(visited[i][j]){
            return false;
        }
        visited[i][j] = true;
        if(board[i][j] == word.charAt(index)){
            return dfs(board, i + 1, j, index + 1, word, visited) ||
                    dfs(board, i - 1, j, index + 1, word, visited) ||
                    dfs(board, i, j + 1, index + 1, word, visited) ||
                    dfs(board, i, j - 1, index + 1, word, visited);
        }else{
            return false;
        }
    }
    static public int getLucky(String s, int k) {
        String num = "";
        for(int i = 0; i < s.length(); i++){
            int cur = s.charAt(i) - 'a' + 1;
            num += String.valueOf(cur);
        }
        while(k > 1){
            int res = toInt(num);
            num = String.valueOf(res);
            k--;
        }
        return toInt(num);
    }

    static public int toInt(String num){
        int sum = 0;
        for(int i = 0; i < num.length(); i++){
            sum += num.charAt(i) - '0';
        }
        return sum;
    }
    static public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int res = 0;
        int cur = 0;
        for(int i = 0; i < n; i++){
            int curMin = nums[i], curMax = nums[i];
            for(int j = i; j < n; j++){
                curMin = Math.min(curMin, nums[j]);
                curMax = Math.max(curMax, nums[j]);
                if(j == i){
                    cur = nums[i] + nums[j];
                }else{
                    cur = curMin + curMax;
                }
                if(cur <= target){
                    res = (res + 1) % (1000000007);
                }
            }
        }
        return res;
    }
    static public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int res = 0, cur = 0;
        int l = 0, r = 0;
        while(r < nums.length){
            int curR = nums[r];
            while(set.contains(curR)){
                int curL = nums[l];
                cur -= curL;
                l++;
                set.remove(curL);
            }
            while(!set.contains(curR)){
                cur += curR;
                res = Math.max(res, cur);
                r++;
                set.add(curR);
            }
        }
        return res;
    }
    static int MOD = 1000000007;
    static public int numOfSubarrays(int[] arr) {
        int odd = 0, even = 0;
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < arr.length; i++){
            if(set.contains(arr[i])){
                continue;
            }
            set.add(arr[i]);
            if(arr[i] % 2 == 0){
                even++;
            }else{
                odd++;
            }
        }
        int[][] dp = new int[odd + 1][even + 1];
        int oddF = factorial(odd);
        for(int i = 1; i < odd + 1; i++){
            if(i % 2 == 1) dp[i][0] = oddF / (factorial(i) * factorial(odd - i)) % MOD;
        }
        int res = 0;
        for(int i = 1; i < odd + 1; i++){
            if(i % 2 == 0) continue;
            for(int j = 1; j < even + 1; j++){
                if(i % 2 == 0){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i][j - 1] * (even - j + 1) % MOD;
                }
            }
        }
        for(int i = 0; i < odd + 1; i++){
            if(i % 2 == 0) continue;
            for(int j = 0; j < even + 1; j++){
                res += dp[i][j] % MOD;
            }
        }
        return res;
    }

    static public int factorial(long number) {
        if (number <= 1)
            return 1;
        else
            return (int)(number * factorial(number - 1) % MOD);
    }
    static public int maxArea1(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        long horizonMax = 0, verticalMax = 0;
        int mod = 1000000007;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);

        for (int i = 1; i < horizontalCuts.length; i++) {
            horizonMax = Math.max(horizonMax, horizontalCuts[i] - horizontalCuts[i - 1]);
        }
        // 补充验证边界切割位置
        horizonMax = Math.max(horizonMax, horizontalCuts[0] - 0);
        horizonMax = Math.max(horizonMax, h - horizontalCuts[horizontalCuts.length - 1]);

        for (int i = 1; i < verticalCuts.length; i++) {
            verticalMax = Math.max(verticalMax, verticalCuts[i] - verticalCuts[i - 1]);
        }
        // 补充验证边界切割位置
        verticalMax = Math.max(verticalMax, verticalCuts[0] - 0);
        verticalMax = Math.max(verticalMax, w - verticalCuts[verticalCuts.length - 1]);

        return (int) ((horizonMax * verticalMax) % mod);
    }
    static public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        long hmax = 0, wmax = 0;
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        for(int i = 0; i <= horizontalCuts.length; i++){
            int pre = i== 0 ?  0 : horizontalCuts[i - 1];
            int cur = i == horizontalCuts.length ? h : horizontalCuts[i];
            hmax = Math.max(hmax, cur - pre);
        }
        for(int i = 0; i <= verticalCuts.length; i++){
            int pre = i == 0 ?  0 : verticalCuts[i - 1];
            int cur = i == verticalCuts.length ? w : verticalCuts[i];
            wmax = Math.max(wmax, cur - pre);
        }
        return (int)((hmax * wmax) % (1e9 + 7));
    }
    static public List<String> findAndReplacePattern(String[] words, String pattern) {
        int n = pattern.length();
        int[] patt = new int[n];
        List<String> res = new LinkedList<>();
        HashMap<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            if(!map.containsKey(pattern.charAt(i))){
                patt[i] = i;
                map.put(pattern.charAt(i), i);
            }else{
                patt[i] = map.get(pattern.charAt(i));
            }
        }
        for(String word : words){
            boolean judge = true;
            Set<Character> set = new HashSet<>();
            if(word.length() != n){
                continue;
            }
            for(int i = 0; i < n; i++){
                char cur = word.charAt(i);
                if(patt[i] != i){//非新字符
                    if(word.charAt(patt[i]) != cur){
                        judge = false;
                        break;
                    }
                }else{
                    if(set.contains(cur)){
                        judge = false;
                        break;
                    }else{
                        set.add(cur);
                    }
                }
            }
            if(judge) res.add(word);
        }
        return res;
    }
    static public String mergeAlternately(String word1, String word2) {
        int n = word1.length() + word2.length();
        StringBuilder res = new StringBuilder();
        int s1 = 0, s2 = 0;
        while(n > 0){
            char curCh;
            if(s1 == word1.length()){
                res.append(word2.substring(s2, word2.length()));
                return res.toString();
            }
            if(s2 == word2.length()){
                res.append(word1.substring(s1, word1.length()));
                return res.toString();
            }
            if(n % 2 == 0){
                curCh = word1.charAt(s1);
                s1++;
            }else{
                curCh = word2.charAt(s2);
                s2++;
            }
            res.append(curCh);
            n--;
        }
        return res.toString();
    }
    static public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        String s2Copy = "";
        for(int i = 0; i < n2; i++){
            s2Copy += s2;
        }
        int index = 0, s1Num = 1;
        //若至少需要两个s1才能满足一个子串，计算最少s1Num个s1可满足子串
        for(int i = 0; i < s2Copy.length(); i++){
            char curCh = s2Copy.charAt(i);
            while(s1.charAt(index) != curCh){
                index++;
                if(index == s1.length()){
                    s1Num++;
                }
                index %= s1.length();
            }
            if(index > 0) s1Num++;
        }
        //若单个s1可满足一个或多个子串，计算单个s1和两个s1满足子串的数量
        index = 0;
        int s2Num = 0, s2NumTwo = 0;
        for(int i = 0; i < s1.length() * 2; i++){
            if(s1.charAt(i % s1.length()) == s2Copy.charAt(index)){
                index++;
                if(index == s2Copy.length()){
                    s2NumTwo++;
                }
                if(i < s1.length() && index == s2Copy.length()){
                    s2Num++;
                }
                index %= s2Copy.length();
            }
        }
        int res = 0;
        if(s2Num > 0){//单个子串可满足子串
            res = s2Num * n1 + (n1 - 1) * (s2NumTwo - 2 * s2Num);
        }else{
            res = n1 / s1Num;
        }
        return res;
    }
    static public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int res = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 1; i < heights.length; i++){
            int curHigh = heights[i] - heights[i - 1];
            if(curHigh > 0){
                queue.offer(curHigh);
                if(ladders > 0){
                    ladders--;
                }else{
                    if(bricks >= queue.peek()){
                        bricks -= queue.poll();
                    }else{
                        return res;
                    }
                }
            }
            res = i;
        }
        return res;
    }
    static public int numTeams(int[] rating) {
        int res = 0;
        int n = rating.length;
        for(int i = 0; i < n; i++){
            int big = 0, small = 0;
            for(int j = i + 1; j < n; j++){
                if(rating[j] > rating[i]){
                    big++;
                }else{
                    small++;
                }
            }
            res += big >= 2 ? big * (big - 1) / 2: 0;
            res += small >= 2 ? small * (small - 1) / 2 : 0;
        }
        return res;
    }
    static public int numDifferentIntegers(String word) {
        Set<String> set = new HashSet<>();
        String curNum = "";
        for(int i = 0; i < word.length(); i++){
            char cur = word.charAt(i);
            if(cur >= '0' && cur <= '9'){
                curNum += cur;
            }else{
                if(curNum.length() == 0){
                    continue;
                }else{
                    for(int j = 0; j < curNum.length(); j++){
                        if(curNum.charAt(j) != '0'){
                            curNum = curNum.substring(j, curNum.length());
                            break;
                        }
                    }
                    if(!set.contains(curNum)){
                        set.add(curNum);
                    }
                    curNum = "";
                }
            }
        }
        if(curNum.length() != 0 && !set.contains(curNum)){
            set.add(curNum);
        }
        return set.size();
    }
    static int res;
    static public int knightDialer(int n) {
        int[][] step = new int[][]{{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}};
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 3; j++){
                if(check(i, j)) dfs(i, j, step, 0, n - 1);
            }
        }
        return res;
    }

    static public void dfs(int i, int j, int[][] step, int start, int n){
        if(n == 0){
            res++;
            res %= (1e9 + 7);
            return;
        }
        for(int k = start; k < step.length; k++){
            if(!check(i + step[k][0], j + step[k][1])){
                continue;
            }
            dfs(i + step[k][0], j + step[k][1], step, k + 1, n - 1);
        }
    }

    static public boolean check(int i, int j){
        if(i < 0 || i > 3 || j < 0 || j > 2) return false;
        if(i == 3 && (j == 0 || j == 2)) return false;
        return true;
    }
    static public long minimalKSum(int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        long res = 0;
        int j = k;
        for(int i = 1; i <= n + k; i++){
            if(!map.containsKey(i)){
                res += i;
                if(--j == 0) break;
            }
        }
        return res;
    }

    static public List<Integer> addToArrayForm(int[] num, int k) {
        int n = num.length;
        long arrVal = 0;
        LinkedList<Integer> res = new LinkedList<>();
        for(int i = 0; i < n; i++){
            arrVal = arrVal * 10 + num[i];
        }
        long sum = arrVal + k;
        while(sum > 0){
            res.addFirst((int)(sum % 10));
            sum /= 10;
        }
        return res;
    }
    static public char findKthBit(int n, int k) {
        String[] strs = new String[n];
        strs[0] = "0";
        for(int i = 1; i < n; i++){
            String s1 = reverse(strs[i - 1]);
            String s2 = "1" + s1;
            strs[i] = strs[i - 1] + s2;
        }
        return strs[n - 1].charAt(k - 1);
    }

    static public String reverse(String str){
        int n = str.length();
        char[] chs = str.toCharArray();
        for(int i = 0; i < n; i++){
            chs[i] = chs[i] == '0' ? '1' : '0';
        }
        int l = 0, r = n - 1;
        while(l < r){
            char temp = chs[l];
            chs[l] = chs[r];
            chs[r] = temp;
            l++;
            r--;
        }
        return String.copyValueOf(chs);
    }
    //static int res = 0;
    static boolean[] visited;
    static public int numDistinct(String s, String t) {
        visited = new boolean[s.length()];
        find(s, t, 0, 0);
        return res;
    }

    static public void find(String s, String t, int ls, int lt){
        if(lt == t.length()){
            res++;
            return;
        }
        if(ls >= s.length() || lt >= t.length()){
            return;
        }

        for(int i = ls; i < s.length(); i++){
            int curS = s.charAt(i);
            int curT = t.charAt(lt);
            if(visited[i]){
                continue;
            }
            if(curS == curT){
                visited[i] = true;
                find(s, t, i + 1, lt + 1);
                visited[i] = false;
            }
        }
    }
    static public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for(int j = 0; j < n; j++){
            dp[m - 1][j] = matrix[m - 1][j];
        }
        for(int i = m - 2; i >= 0; i--){
            for(int j = 0; j < n; j++){
                int curMin = matrix[i][j] + dp[i + 1][j];
                for(int k = j - 1; k <= j + 1; k++){
                    if(k < 0 || k >= n ){
                        continue;
                    }
                    curMin = Math.min(curMin, matrix[i][j] + dp[i + 1][k]);
                }
                dp[i][j] = curMin;
            }
        }
        int res = dp[0][0];
        for(int j = 1; j < n; j++){
            Math.min(res, dp[0][j]);
        }
        return res;
    }
    static public String multiply(String num1, String num2) {
        return toString(toNum(num1) * toNum(num2));
    }

    static public long toNum(String str){
        int n = str.length();
        long num = 0;
        for(int i = 0; i < n; i++){
            num *= 10;
            num += str.charAt(i) - '0';
        }
        return num;
    }

    static public String toString(long num){
        return "" + num;
    }

//    static int[][] visited;
//    static int res = 0;
//    static public int uniquePathsIII(int[][] grid) {
//        visited = new int[grid.length][grid[0].length];
//        for(int i = 0; i < grid.length; i++){
//            for(int j = 0; j < grid[0].length; j++){
//                if(grid[i][j] == 1){
//                    find(i, j, grid);
//                    return res;
//                }
//            }
//        }
//        return 0;
//    }
//    static public void find(int i, int j, int[][] grid){
//        if(i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1){
//            return;
//        }
//        if(visited[i][j] == -1 || grid[i][j] == -1){
//            return;
//        }
//        if(grid[i][j] == 2){
//            res++;
//        }
//        visited[i][j] = -1;
//        find(i + 1, j, grid);
//        find(i - 1, j, grid);
//        find(i, j + 1, grid);
//        find(i, j - 1, grid);
//        visited[i][j] = 0;
//    }

    static HashMap<Integer, Integer> map = new HashMap<>();
    static public int scoreOfStudents(String s, int[] answers) {
        int ans = result(s);
        findAndGetRinght(s, 1, s.length() - 2, 0, 0);
        int res = 0;
        for(int i = 0; i < answers.length; i++){
            if(answers[i] == ans){
                res += 5;
            }else if(map.containsKey(answers[i])){
                res += 2;
            }
        }
        return res;
    }

    static public int result(String s){
        Deque<Integer> q = new LinkedList();
        Deque<Character> cq = new LinkedList();
        int idx = 0;
        for(int i = 0;i < s.length();i ++){
            if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
                q.offerFirst(s.charAt(i) - '0');
                if(!cq.isEmpty() && cq.peekFirst() == '*'){
                    int n1 = q.pollFirst();
                    int n2 = q.pollFirst();
                    q.offerFirst(n1 * n2);
                    cq.pollFirst();
                }
            }else{
                cq.offerFirst(s.charAt(i));
            }
        }
        while(!cq.isEmpty()){
            int n1 = q.pollFirst();
            int n2 = q.pollFirst();
            q.offerFirst(n1 + n2);
            cq.pollFirst();
        }
        return q.peekFirst();
    }

    static public void findAndGetRinght(String s, int start, int end, int count, int temp){
        if(start < 1 || end > s.length() - 2){
            return;
        }
        if(count == (s.length() - 1) / 2){
            if(!map.containsKey(temp)){
                map.put(temp, 1);
            }
            return;
        }
        for(int i = start; i <= end; i += 2){
            int left = s.charAt(i - 1) - '0';
            int right = s.charAt(i + 1) - '0';
            if(s.charAt(i) == '+'){
                temp += left + right;
            }else if(s.charAt(i) == '*'){
                temp += left * right;
            }
            findAndGetRinght(s, start, i - 2, count++, temp);
            findAndGetRinght(s, i + 2, end, count++, temp);
            if(s.charAt(i) == '+'){
                temp -= left + right;
            }else if(s.charAt(i) == '*'){
                temp -= left * right;
            }
        }
    }
    static public int constrainedSubsetSum(int[] nums, int k) {
        int n = nums.length;
        int res = nums[0];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++){
            dp[i] = nums[i];
            for(int j = i - 1; j >= 0 && j >= i - k; j--){
                dp[i] = Math.max(dp[j] + nums[i], dp[i]);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
     static public String longestPalindrome(String s) {
        char[] str = s.toCharArray();
        String res = "";
        for(int i = 0; i < s.length(); i++){
            for(int j = 0; j <= 1; j++){
                int l = i, r = i + j;
                while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                    if(res.length() < r - l + 1){
                        res = s.substring(l, r + 1);
                    }
                    l--;
                    r++;
                }
            }
        }
        return res;
    }

    static public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        ArrayList<int[]> res = new ArrayList<>();
        for(int[] first : firstList){
            for(int[] second : secondList){
                if(first[0] > second[1]){
                    continue;
                }else if(first[1] < second[0]){
                    break;
                }else{
                    int[] temp = new int[2];
                    temp[0] = Math.max(first[0], second[0]);
                    temp[1] = Math.min(first[1], second[1]);
                    res.add(temp);
                }
            }
        }
        return res.toArray(new int[res.size()][]);
    }
    static public boolean isAdditiveNumber(String num) {
        ArrayList<Integer> list = new ArrayList<>();
        return find(num, list, num.length(), 0, 0, 0);
    }
    static public boolean find(String num, ArrayList<Integer> list, int length, int index, int sum, int pre){
        if(index >= length){
            return list.size() >= 3;
        }
        long curLong = 0;
        for(int i = index; i < length; i++){
            if(i > index && num.charAt(index) == '0'){
                break;
            }
            curLong = curLong * 10 + num.charAt(i) - '0';
            if(curLong > Integer.MAX_VALUE){
                break;
            }
            int curNum = (int) curLong;
            if(list.size() >= 2){
                if(curNum < sum){
                    continue;
                }else if(curNum > sum){
                    break;
                }
            }
            list.add(curNum);
            if(find(num, list, length, i + 1, curNum + pre, curNum)){
                return true;
            }else{
                list.remove(list.size() - 1);
            }
        }
        return false;
    }
    static public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return res;
        }
        queue.offer(root);
        int t = 1;
        while(!queue.isEmpty()){
            int n = queue.size();
            List<Integer> temp = new LinkedList<>();
            for(int i = 0; i < n; i++){
                TreeNode cur = queue.poll();
                if(t % 2 == 1){
                    temp.add(cur.val);
                }else{
                    temp.add(0, cur.val);
                }
                if(cur.left != null) queue.offer(cur.left);
                if(cur.right != null) queue.offer(cur.right);
            }
            t++;
            res.add(temp);
        }
        return res;
    }
    static public boolean isUgly(int n) {
        while(n >= 5){
            if(n % 2 == 0){
                n = n / 2;
                continue;
            }
            if(n % 3 == 0){
                n = n / 3;
                continue;
            }
            if(n % 5 == 0){
                n = n / 5;
                continue;
            }
        }
        return n == 2 || n == 3;
    }
    static public int trailingZeroes(int n) {
        int count = 0;
        while(n > 0){
            count += n / 5;
            n = n / 5;
        }
        return count;
    }
    static public int preimageSizeFZF(int k) {
        //5, 26, 27, 128, 129, 130
        //5 + 0; 25 + 1; 125 + 3,
        //4, 1 + 1; 19, 2 + 1; 99, 3 + 1;
        int i = 1;
        int min = -1;
        int max = -1;
        while(max < k){
            min = 5 ^ i + 2 ^ (i - 1) - 1;
            max = min + i - 1;
            i++;
        }
        return k >= min ? 0 : 5;
    }

    static public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        List<List<Integer>> res = new LinkedList<>();
        boolean[][] board = new boolean[8][8];
        for(int[] queen : queens){
            board[queen[0]][queen[1]] = true;
        }
        int[][] moveArr = new int[][]{
                {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}
        };
        for(int[] move : moveArr){
            int[] cur = new int[]{king[0], king[1]};
            while(cur[0] >= 0 && cur[0] < 8 && cur[1] >= 0 && cur[1] < 8){
                if(board[cur[0]][cur[1]]){
                    List<Integer> temp = new LinkedList<Integer>(Arrays.asList(cur[0], cur[1]));
                    res.add(temp);
                    break;
                }else{
                    cur[0] += move[0];
                    cur[1] += move[1];
                }
            }
        }
        return res;
    }
    static public int[] singleNumber(int[] nums) {
        int[] rst = new int[2];
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            res ^= nums[i];
        }
        int sum = Math.abs(res);
        for(int i = 0; i < nums.length; i++){
            if(sum >= Math.abs(res ^ nums[i])){
                rst[0] = nums[i];
                rst[1] = res ^ nums[i];
            }
        }
        return rst;
    }
    static public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            res += (n & 1) == 1? 1 : 0;
            n = (n >>> 1);
        }
        return res;
    }
    static class LFUCache {
        private HashMap<Integer, Node> keyNode = new HashMap<>();
        private HashMap<Integer, DoubleList> numList = new HashMap<>();
        private int capacity;
        public LFUCache(int capacity) {
            this.capacity = capacity;
            numList.put(1, new DoubleList());
        }

        public int get(int key) {
            if(!keyNode.containsKey(key)){//若不存在，返回-1
                return -1;
            }
            //若存在，访问频次+1，变换位置
            Node cur = keyNode.get(key);
            update(cur);
            return cur.val;
        }

        public void put(int key, int value) {
            if(keyNode.containsKey(key)){
                Node cur = keyNode.get(key);
                cur.val = value;
                update(cur);
            }else{
                capacity--;
                if(capacity < 0){
                    if(keyNode.size() != 0){
                        removeOld();
                    }else{
                        return;
                    }
                    capacity = 0;
                }
                Node node = new Node(key, value);
                keyNode.put(key, node);
                numList.get(1).addLast(node);
            }
        }
        /**
         删除访问次数最少的，若次数一样则删最久未访问的
         */
        public void removeOld(){
            if(capacity > 0){
                return;
            }
            int num = 1;
            while(numList.get(num).size() == 0){
                num++;
            }
            DoubleList curList = numList.get(num);
            int firstKey = curList.getFirstKey();
            keyNode.remove(firstKey);
            numList.get(num).removeFirst();
        }


        /**
         访问某一节点后，更新其次数和位置
         */
        public void update(Node node){//更新节点访问次数，位置
            int num = node.num;
            numList.get(num).remove(node);
            node.num++;
            if(!numList.containsKey(node.num)){
                numList.put(node.num, new DoubleList());
            }
            numList.get(node.num).addLast(node);
        }
    }
    static class DoubleList{//双向链表
        private Node head, tail;
        private int size;

        public DoubleList(){
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.pre = head;
            size = 0;
        }

        public void addLast(Node node){
            node.pre = tail.pre;
            node.next = tail;
            tail.pre.next = node;
            tail.pre = node;
            size++;
        }

        public void remove(Node node){
            node.next.pre = node.pre;
            node.pre.next = node.next;
            size--;
        }

        public Node removeFirst(){
            if(head.next == null){
                return null;
            }
            Node first = head.next;
            remove(first);
            return first;
        }

        public int getFirstKey(){
            return head.next.key;
        }

        public int size(){
            return size;
        }
    }


    static class Node{//节点
        public Node pre;
        public Node next;
        public int key;
        public int val;
        public int num;//访问频次
        public Node(int key, int val){
            this.key = key;
            this.val = val;
            this.num = 1;
        }
    }



    static class LRUCache {
        HashMap<Integer, Integer> map;
        LinkedList<Integer> list;
        int capacity;
        public LRUCache(int capacity) {
            this.map = new HashMap<>();
            this.list = new LinkedList<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            if(map.containsKey(key)){
                int index = map.get(key);
                update(index);
                int value = list.get(index);
                list.remove(index);
                list.addFirst(value);
                map.put(key, 0);
                return value;
            }else{
                return -1;
            }
        }

        public void put(int key, int value) {
            if(map.containsKey(key)){
                int index = map.get(key);
                update(index);
                list.remove(index);
                list.addFirst(value);
                map.put(key, 0);
            }else{
                if(capacity > 0){
                    update(Integer.MAX_VALUE);
                    map.put(key, 0);
                    list.addFirst(value);
                    capacity--;
                }else{
                    removeLast();
                    update(Integer.MAX_VALUE);
                    list.addFirst(value);
                    list.removeLast();
                    map.put(key, 0);
                }
            }
        }

        public void update(int index){
            for(int key : map.keySet()){
                if(map.get(key) < index){
                    map.put(key, map.get(key) + 1);
                }
            }
        }

        public void removeLast(){
            int lastIndex = -1;
            int lastKey = -1;
            for(int key : map.keySet()){
                if(map.get(key) > lastIndex){
                    lastKey = key;
                    lastIndex = map.get(key);
                }
            }
            map.remove(lastKey);
        }
    }
    public static int maxProfit1(int k, int[] prices) {
        int[] buy = new int[k];
        int[] sell = new int[k];
        for(int i=0;i < buy.length; i++){
            buy[i] = Integer.MIN_VALUE;
        }
        for(int p : prices){
            buy[0] = Math.max(buy[0], -p);
            sell[0] = Math.max(sell[0], buy[0] + p);
            for(int i = 1; i < k; i++){
                buy[i] = Math.max(buy[i], sell[i - 1] - p);
                sell[i] = Math.max(sell[i], buy[i] + p);
            }
        }
        return sell[k-1];
    }

    public static int maxProfit(int[] prices) {
        int[] dp = new int[prices.length + 1];
        dp[0] = 0;
        for(int i = 1; i < dp.length; i++){
            for(int j = i; j > 0; j--){
                int temp = 0;
                if(prices[i - 1] - prices[j - 1] + dp[j - 1] > dp[i - 1]){//当前价格卖出之前某一天买入的股票+买入之前的最大收益
                    temp = prices[i - 1] - prices[j - 1] + dp[j - 1];
                }else{
                    temp = dp[i - 1];
                }
                dp[i] = Math.max(dp[i], temp);
            }
        }
        return dp[prices.length];
    }

    public static int findKthLargest(int[] nums, int k) {
        int index = nums.length - k;
        sort(nums, 0, nums.length - 1, index);
        return nums[index];
    }

    public static void sort(int[] nums, int start, int end, int index){
        if(start > end){
            return;
        }
        int p = partition(nums, start, end);
        sort(nums, p + 1, end, index);
        sort(nums, start, p - 1, index);
    }

    public static int partition(int[] nums, int start, int end){
        int temp = nums[end];
        int left = 0;
        int right = end;
        while(left < right){
            while(nums[left] <= temp && left < right){
                left++;
            }
            nums[right] = nums[left];
            while(nums[right] >= temp && left < right){
                right--;
            }
            nums[left] = nums[right];
        }
        nums[left] = temp;
        return left;
    }


    public static List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return builder(1, n);
    }

    public static List<TreeNode> builder(int start, int end){
        List<TreeNode> temp = new ArrayList<>();
        if(start > end){
            temp.add(null);
            return temp;
        }
        int rootVal = start;
        while(rootVal <= end){
            List<TreeNode> leftList = builder(start, rootVal - 1);
            List<TreeNode> rightList = builder(rootVal + 1, end);
            for(TreeNode left : leftList){
                for(TreeNode right : rightList){
                    TreeNode root = new TreeNode(rootVal);
                    root.left = left;
                    root.right = right;
                    temp.add(root);
                }
            }
            rootVal++;
        }
        return temp;
    }

    public static int countRangeSum(int[] nums, int lower, int upper) {
        int res = 0;
        long[] preSum = new long[nums.length + 1];
        preSum[0] = 0;
        for(int i = 1; i < preSum.length; i++){
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for(int i = 0; i < preSum.length; i++){
            for(int j = i + 1; j < preSum.length; j++){
                long sum = preSum[j] - preSum[i];
                if(sum >= lower && sum <= upper){
                    res++;
                }
            }
        }
        return res;
    }
    public static String smallestSubsequence(String s) {
        int left = 0;
        int right = 0;
        int n = s.length();
        int[] abc = new int[26];
        while(right < n){
            char end = s.charAt(right);
            int endIndex = end - 'a';
            abc[endIndex]++;
            right++;
            while(abc[endIndex] > 1){
                char pre = s.charAt(left);
                int preIndex = pre - 'a';
                if(abc[preIndex] == 1){
                    break;
                }
                abc[preIndex]--;
                left++;
            }
        }
        String res = "";
        for(int i = left; i < right; i++){
            char cur = s.charAt(i);
            int curIndex = cur - 'a';
            if(abc[curIndex] != -1){
                res += cur;
                abc[curIndex] = -1;
            }
        }
        return res;
    }
    public static int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for(int i = 0; i < piles.length; i++){
            if(right < piles[i]){
                right = piles[i];
            }
        }
        int k = right;
        while(left < right){
            int mid = left + (right - left) / 2;
            long need = 0;
            for(int i = 0; i < piles.length; i++){
                if(piles[i] <= mid){
                    need++;
                }else{
                    need +=  piles[i] / mid + 1;
                }
            }
            if(need <= h){
                k = mid;
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return k;
    }





    public static String minWindow(String s, String t) {
        int[] strT = new int[52];
        int num = 0;
        for(int i = 0; i < t.length(); i++){
            int indexT = getIndex(t.charAt(i));
            if(strT[indexT] == 0){
                num++;
            }
            --strT[indexT];
        }
        int left = 0;
        int right = 0;
        int start = 0;
        int valid = 0;
        int strMin = Integer.MAX_VALUE;
        while(right < s.length()){
            char end = s.charAt(right);
            int indexEnd = getIndex(end);
            if(strT[indexEnd] == -1){
                valid++;
            }
            strT[indexEnd]++;
            right++;
            while(strT[indexEnd] > 1){
                char pre = s.charAt(left);
                int indexPre = getIndex(pre);
                if(strT[indexPre] == 1){
                    valid--;
                }
                strT[indexPre]--;
                left++;
            }
            if(valid == num ){
                valid = 0;
                if(strMin > right - left){
                    strMin = right - left;
                    start = left;
                }
            }
        }
        return strMin == Integer.MAX_VALUE? "" : s.substring(start, start + strMin);
    }

    public static int getIndex(char ch){
        if(ch > 96 && ch < 123){//小写
            return ch - 'a';
        }else{//大写
            return ch - 'A' + 26;
        }
    }

    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        HashMap<Character, Integer> map = new HashMap<>();
        int lenMax = 0;
        int left = 0;
        int right = 0;
        while(right < n){
            char end = s.charAt(right);
            if(!map.containsKey(end)){
                map.put(end, 1);
            }else{
                map.put(end, map.get(end) + 1);
            }
            right++;
            while(map.get(end) > 1){
                char pre = s.charAt(left);
                map.put(pre, map.get(pre) - 1);
                left++;
            }
            if(lenMax < right - left){
                lenMax = right - left;
            }
        }
        return lenMax;
    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] strP = new int[26];
        for(int i = 0; i < p.length(); i++){
            strP[p.charAt(i) - 'a']--;
        }
        int left = 0;
        int right = 0;
        while(right < s.length()){
            char end = s.charAt(right);
            int endIndex = end - 'a';
            strP[endIndex]++;
            right++;
            while(strP[endIndex] > 0){
                char pre = s.charAt(left);;
                int preIndex = pre - 'a';
                strP[preIndex]--;
                left++;
            }
            if(right - left == p.length()){
                res.add(left);
            }
        }
        return res;
    }

    public static String reverseWords(String s) {
        String res = "";
        char[] str = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        while(left < right){
            if (str[left] == ' '){
                left++;
            }
            if (str[right] == ' '){
                right--;
            }
            if(str[left] != ' ' && str[right] != ' '){
                break;
            }
        }
        reverseLR(str, left, right);
        int pre = left;
        int end = left;
        while(end <= right){
            if (pre == -1){
                if(str[end] != ' '){
                    pre = end;
                }
                end++;
                continue;
            }
            if(str[end] == ' ' || end == right){
                int endIndex = end == right ? right : end - 1;
                reverseLR(str, pre, endIndex);
                pre = -1;
                if(end == right){
                    break;
                }
            }
            end++;
        }
        for(int i = left; i <= right; i++){
            res += str[i];
        }
        return res;
    }

    public static void reverseLR(char[] str, int left, int right){
        while(left < right){
            char temp = str[left];
            str[left] = str[right];
            str[right] = temp;
            left++;
            right--;
        }
    }
    public static int[] corpFlightBookings(int[][] bookings, int n) {
        int[] answer = new int[n];
        int[] diff = new int[n];
        for(int i = 0; i < bookings.length; i++){
            int left = bookings[i][0];
            int right = bookings[i][1];
            int val = bookings[i][2];
            diff[left - 1] += val;
            diff[right - 1] -= val;
        }
        answer[0] = diff[0];
        for(int i = 1; i < diff.length; i++){
            answer[i] = answer[i - 1] + diff[i];
        }
        return answer;
    }

    public static boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for(int i = 0; i < trips.length; i++){
            int val = trips[i][0];
            int left = trips[i][1];
            int right = trips[i][2];
            diff[right] -= val;
            diff[left] += val;
        }
        int res = diff[0];
        if(res > capacity){
            return false;
        }
        for(int i = 1; i < diff.length; i++){
            res += diff[i];
            if(res > capacity){
                return false;
            }
        }
        return true;
    }
    public static boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head, pre = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        while(slow != null){
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        while(head != null && pre != null){
            if(head.val !=  pre.val ){
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;
    }

    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
    public static int coinChange(int[] coins, int amount) {
        int[][] dp = new int[amount + 1][coins.length + 1];
        for(int i = 0; i < coins.length + 1; i++){//总金额为0，数目为0
            dp[0][i] = 0;
        }
        for(int i = 0; i < amount + 1; i++){//面值为0，数目为-1
            dp[i][0] = -1;
        }
        /***
         *   0  1  2  5
         * 0 0  0  0  0
         * 1 -1 1
         * 2 -1
         * 3 -1
         */
        for(int i = 1; i < amount + 1; i++){
            for(int j = 1; j < coins.length + 1; j++){
                if(i < coins[j - 1]){
                    dp[i][j] = dp[i][j - 1];
                }else{
                    int num1 = i / coins[j - 1];//当前面值,硬币数量
                    int val = i % coins[j - 1];//剩余面值
                    int num2 = 0;
                    if(val != 0){
                        num2 = dp[val][j - 1];//剩余面值，最小硬币数量
                    }
                    while(num2 == -1 && num1 > 0){//剩余面值无解且，当前面值数量不为0
                        num1--;//减少当前面值数量
                        val += coins[j - 1];//增加剩余面值
                        num2 = dp[val][j - 1];//剩余面值，最小硬币数量
                    }
                    if(num2 == -1){
                        dp[i][j] = -1;
                    }else{
                        dp[i][j] = num1 + num2;
                    }
                }
                System.out.print(dp[i][j]+ "\t");
            }
            System.out.println();
        }
        return dp[amount][coins.length];
    }
    public static int maxJumpGrade (ArrayList<Integer> nums) {
        // write code here
        int n = nums.size();
        if (n < 1) {
            return -1;
        }
        if (n == 1) {
            return nums.get(0);
        }
        int[] dpTable = new int[n];
        for (int i = 0; i < n - 1;
             i++) { //依次更换起跳点(最后一点不为起跳点)
            for (int j = i; j <= i + nums.get(i); j++) { //依次更换落点
                if (i == j) continue;
                if (dpTable[j] < dpTable[i] + nums.get(i)) {//原价值小于新价值
                    //起跳点积分+跳跃积分>原跳跃积分
                    dpTable[j] = dpTable[i] + nums.get(i);
                }
                for (int k = 0; k < n; k++){
                    System.out.print(dpTable[k] + "\t");
                }
                System.out.println();
            }
        }
        if (dpTable[n - 1] == 0) { //未跳到最后一点
            return -1;
        } else {
            return dpTable[n - 1] + nums.get(n - 1);
        }
    }

    public static class stackk {
        Stack<Integer> stack = new Stack<Integer>();
        Stack<Integer> minStack = new Stack<Integer>();
        public void push(int node) {
            stack.add(node);
            if (minStack.size() < 1 || minStack.peek() >= node) {
                minStack.add(node);
            } else {
                int n = 0;
                while (minStack.peek() < node) {
                    stack.add(minStack.pop());
                    n++;
                    if(minStack.size() < 1){
                       break;
                    }
                }
                minStack.add(node);
                while (n > 0) {
                    minStack.add(stack.pop());
                    n--;
                }
            }
        }

        public void pop() {
            int num = stack.pop();
            int n = 0;
            while (minStack.peek() != num) {
                stack.add(minStack.pop());
                n++;
            }
            minStack.pop();
            while (n > 0) {
                minStack.add(stack.pop());
                n--;
            }
        }

        public int top() {
            return stack.peek();
        }

        public int min() {
            return minStack.peek();
        }
    }

    public static boolean palindrome(String str) {
        // write code here
        char[] nums = str.toCharArray();
        int left = 0;
        int right = nums.length - 1;
        int count = 0;
        while (left < right) {
            if (nums[left] != nums[right]) {
                count++;
            }
            left++;
            right--;
            if (count > 1) {
                return false;
            }
        }
        return  true;
    }
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public static class UF{
        int count;
        int[] father;

        public UF(int count) {
            this.count = count;
            this.father = new int[count];
            for (int i = 0; i < count; i++){
                father[i] = i;
            }
        }

        public int find(int v){
            return father[v] == v ? v : find(father[v]);
        }

        public boolean union(int p, int q){
            if(find(p) == find(q)){
                return false;
            }
            count--;
            father[find(p)] = find(q);
            return true;
        }

        public boolean connected(int p, int q){
            return find(p) == find(q);
        }

        public int getCount(){
            return count;
        }
    }
}
